/*
Copyleft 2006 by T.S.Yo
*/


package exp.util;
import java.io.*;
import java.util.*;
import ec.*;
import ec.util.*;
import ec.simple.*;
import ec.Initializer;
import ec.Individual;
import ec.BreedingPipeline;
import ec.Breeder;
import ec.EvolutionState;
import ec.Population;
import ec.util.Parameter;

/* 
 * MyExpBreeder.java
 * 
 * Created: 2007.02.05
 * By: T.S.Yo
 */

/**
 * MyExpBreeder define customized breeding method:
 * 
 * - no elitism
 * - no multi-thread
 * - generates offsprings with default settings, and forms another population
 * - final selection on the union of the original population plus the newly generated population
 *
 * @author T.S.Yo
 * @version 1.0 
 */

public class MyExpBreeder extends SimpleBreeder
{
    // Define parameter names
    public void setup(final EvolutionState state, final Parameter base) 
    {
        super.setup(state, base);
    }

    
    // Constructor
    
    public Population breedPopulation(EvolutionState state) 
    {
        // Parameters for multi-thread breeding
        int numinds[][] = 
            new int[state.breedthreads][state.population.subpops.length];
        int from[][] = 
            new int[state.breedthreads][state.population.subpops.length];
        // Empty new population
        Population newpop = (Population) state.population.emptyClone();
        Population nextpop = (Population) state.population.emptyClone();
                
        // For each breedthread
        for(int y=0;y<state.breedthreads;y++)
        {
            // For each sub-population
            for(int x=0;x<state.population.subpops.length;x++)
            {
                // the number of individuals we need to breed = pop_size
                int length = state.population.subpops[x].individuals.length;
                // For multi-thread breeding:
                // the size of each breeding chunk except the last one
                int firstBreedChunkSizes = length/state.breedthreads;
                // the size of the last breeding chunk
                int lastBreedChunkSize = 
                    firstBreedChunkSizes + length - firstBreedChunkSizes * (state.breedthreads);
                
                // figure numinds
                if (y < state.breedthreads-1) // not the last one
                    numinds[y][x] = firstBreedChunkSizes;
                else // the last one
                    numinds[y][x] = lastBreedChunkSize;
                
                // figure from
                from[y][x] = (firstBreedChunkSizes * y);
            }
        }
        
        // Check if multi-thread breeding    
        if (state.breedthreads==1)
        {
            breedPopChunk(newpop,state,numinds[0],from[0],0);
        } else {
            Thread[] t = new Thread[state.breedthreads];
                
            // start up the threads
            for(int y=0;y<state.breedthreads;y++)
            {
                MyExpBreederThread r = new MyExpBreederThread();
                r.threadnum = y;
                r.newpop = newpop;
                r.numinds = numinds[y];
                r.from = from[y];
                r.me = this;
                r.state = state;
                t[y] = new Thread(r);
                t[y].start();
            }
                
            // gather the threads
            for(int y=0;y<state.breedthreads;y++) try
            {
                t[y].join();
            }
            catch(InterruptedException e)
            {
                state.output.fatal("Whoa! The main breeding thread got interrupted!  Dying...");
            }
        }
        
        // Select from the union of the original population plus the newly generated population
        // Create the united population
        //EvolutionState tmpstate = (EvolutionState)state.clone();
        for(int x=0;x<state.population.subpops.length;x++)
        {
            int l1 = state.population.subpops[x].individuals.length;
            int l2 = newpop.subpops[x].individuals.length;
            Individual[] upop = new Individual[l1+l2];
            // Copy old population
            for(int y=0;y<l1;y++)
            {
                upop[y] = (Individual)state.population.subpops[x].individuals[y].clone();
            }
            // Copy new population
            for(int y=0;y<l2;y++)
            {
                upop[y+l1] = (Individual)newpop.subpops[x].individuals[y].clone();
            }
            // Replace the population with the union
            state.population.subpops[x].individuals = upop.clone();
        }
        // Evaluate the united population
        state.evaluator.evaluatePopulation(state);
        // Print for testing
        //for (int y=0;y<state.population.subpops[1].individuals.length;y++)
        //{
        //    ec.Individual i = state.population.subpops[1].individuals[y];
        //    i.printIndividual(state,state.output.addLog(Log.D_STDOUT,0,false),100);
        //}
        
        // Select from the united population
        // For each sub-population
        for(int x=0;x<state.population.subpops.length;x++)
        {
            // Number of individuals to be selected
            int nToSelect = nextpop.subpops[x].individuals.length;
            // Sort individuals via fitness
            final Individual[] upop = state.population.subpops[x].individuals;
            int[] sortedPop = new int[upop.length];
            QuickSort.qsort(sortedPop, new EliteComparator(state.population.subpops[x].individuals));
            // Select
            breedPopChunk(nextpop,state,numinds[0],from[0],0);
            //System.out.println("Select best: "+nToSelect);
            //for(int y=0;y<nToSelect;y++)
            //    nextpop.subpops[x].individuals[y] = (Individual)(upop[sortedPop[x]].clone());
        }
        // Print for testing
        //for (int y=0;y<state.population.subpops[1].individuals.length;y++)
        //{
        //    ec.Individual i = state.population.subpops[1].individuals[y];
        //    i.printIndividual(state,state.output.addLog(Log.D_STDOUT,0,false),100);
        //}
        state.population = newpop;
        System.out.println("Temp pop 0 size: "+state.population.subpops[0].individuals.length);
        
        // Return the population for next generation
        return nextpop;
    }

    class EliteComparator implements SortComparatorL
        {
        Individual[] inds;
        public EliteComparator(Individual[] inds) {super(); this.inds = inds;}
        public boolean lt(long a, long b)
            { return inds[(int)b].fitness.betterThan(inds[(int)a].fitness); }
        public boolean gt(long a, long b)
            { return inds[(int)a].fitness.betterThan(inds[(int)b].fitness); }
        }

    /** A private helper function for breedPopulation which breeds a chunk
        of individuals in a subpopulation for a given thread.
        Although this method is declared
        public (for the benefit of a private helper class in this file),
        you should not call it. */
    public void breedPopChunk(Population newpop, EvolutionState state,
                              int[] numinds, int[] from, int threadnum) 
    {
        // For each sub-population
        for(int subpop=0;subpop<newpop.subpops.length;subpop++)
        {
            BreedingPipeline bp = (BreedingPipeline)newpop.subpops[subpop].
                                                    species.pipe_prototype.clone();
                
            // check to make sure that the breeding pipeline produces
            // the right kind of individuals.  Don't want a mistake there! :-)
            int x;
            if (!bp.produces(state,newpop,subpop,threadnum))
                state.output.fatal("The Breeding Pipeline of subpopulation " + subpop + 
                                   " does not produce individuals of the expected species " + 
                                   newpop.subpops[subpop].species.getClass().getName() + 
                                   " or fitness " + newpop.subpops[subpop].f_prototype );
            bp.prepareToProduce(state,subpop,threadnum);
                
            // start breedin'!                
            x = from[subpop];
            int upperbound = from[subpop] + numinds[subpop];
            while(x<upperbound)
                x += bp.produce(1,upperbound-x,x,subpop,
                                newpop.subpops[subpop].individuals,
                                state,threadnum);
            if (x>upperbound) // uh oh!  Someone blew it!
                state.output.fatal("Whoa!  A breeding pipeline overwrote the space "+
                                   "of another pipeline in subpopulation " + subpop + 
                                   ".  You need to check your breeding pipeline code (in produce() ).");
            bp.finishProducing(state,subpop,threadnum);
        }
    }
}

// A private helper class for implementing multithreaded breeding 
class MyExpBreederThread implements Runnable
{
    Population newpop;
    public int[] numinds;
    public int[] from;
    public MyExpBreeder me;
    public EvolutionState state;
    public int threadnum;
    public void run()
    {
        me.breedPopChunk(newpop,state,numinds,from,threadnum);
    }
}
